package io.zouyalong.algo.leetcode;

/**
 * https://leetcode-cn.com/problems/wildcard-matching/
 *
 *
 * https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode/
 */
public class WildcardMatching {
    public static void main(String[] args) {
        var target = "1232vbadfdfd";
        var pattern = "*32*fdfd";
        var inst = new WildcardMatching();
        System.out.printf("Matched: %s\n", inst.solution1DP(target, pattern));
        System.out.printf("solution2: %s\n", inst.solution2BackTrace(target, pattern));
    }

    public boolean solution1DP(String s, String p) {
        if (s.length() == 0 && p.length() == 0) {
            return true;
        }
        if (p.length() == 0) {
            return false;
        }
        // 表示从 s[i] 开始的后缀与 p[j]开始的后缀是否匹配
        var suffixMatch = new boolean[s.length() + 1][p.length() + 1];
        suffixMatch[s.length()][p.length()] = true;
        var sArray = s.toCharArray();
        var pArray = p.toCharArray();
        for (int j = pArray.length - 1; j >= 0; j--) {
            if (pArray[j] == '*') {
                suffixMatch[sArray.length][j] = suffixMatch[sArray.length][j+1];
            }
            for (int i = sArray.length - 1; i >= 0; i--) {
                if (pArray[j] == '*') {
                    var matched = false;
                    for (int k = i + 1; k <= sArray.length; k++) {
                        if (suffixMatch[k][j + 1]) {
                            matched = true;
                            break;
                        }
                    }
                    if (!matched) {
                        // * 匹配到空串，即不影响原有匹配
                        matched = suffixMatch[i][j+1];
                    }
                    suffixMatch[i][j] = matched;
                } else if (pArray[j] == '?' || pArray[j] == sArray[i]) {
                    suffixMatch[i][j] = suffixMatch[i + 1][j + 1];
                }
            }
        }
        return suffixMatch[0][0];
    }

    public boolean solution2BackTrace(String s, String p) {
        if (s.length() == 0 && p.length() == 0) {
            return true;
        }
        if (p.length() == 0) {
            return false;
        }
        var backTraceIndex = -1;
        var pStarIdx = -1;
        int sIdx = 0, pIdx = 0;
        var sLen = s.length();
        var pLen = p.length();
        for (; sIdx < sLen;) {
            if (pIdx < pLen && p.charAt(pIdx) == '*') {
                backTraceIndex = sIdx;
                pStarIdx = pIdx;
                pIdx++;
            } else if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))) {
                pIdx++;
                sIdx++;
            } else if (backTraceIndex < 0) {
                return false;
            } else {
                sIdx = backTraceIndex+1;
                pIdx = pStarIdx +1;
                backTraceIndex = sIdx;
            }
        }
        for (; pIdx < p.length() && p.charAt(pIdx) == '*'; pIdx++);
        if (pIdx == p.length()) {
            return true;
        }
        return false;
    }
}
